package exercises.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <a href="https://leetcode-cn.com/problems/non-overlapping-intervals/">
 * 435. 无重叠区间</a>

 * <p><span color="#87CEEB">描述:</span>
 * 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
 * <p>
 * 注意:
 * <p>
 * 可以认为区间的终点总是大于它的起点。
 * 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
 *
 * @author or2
 * @date 2021年10月24日 时间: 15:53
 */
public class No435 {
    public int eraseOverlapIntervals(int[][] intervals) {
        /* 排序 */
        Arrays.sort(intervals, (o1, o2) -> {
            int sub = o1[0] - o2[0];
            if (sub != 0)
                return sub;
            return o2[1] - o1[1];
        });
        /* 去重 */
        var set = new HashSet<Integer>();
        List<int[]> collect = Arrays.stream(intervals).filter(ranges -> {
            if (set.contains(ranges[0]))
                return false;

            set.add(ranges[0]);
            return true;
        }).collect(Collectors.toList());
        /* 去除区间 */
        int remove = 0, rMax = collect.get(0)[1];
        for (int[] range : collect) {
            if (range[1] < rMax)
                remove++;
            rMax = range[1];
        }
        int rest = collect.size() - remove;
        /* TODO 区间交接的，进行合并，在进行去重一次 */
        var map = new HashMap<Integer, int[]>();
        collect = collect.stream().filter(range -> {
            if (map.containsKey(range[0])) {
                map.get(range[0])[1] = range[1];
                map.put(range[1], map.remove(range[0]));
                return false;
            }
            map.put(range[1], range);
            return true;
        }).collect(Collectors.toList());
        /* 去除区间 */
        rMax = collect.get(0)[1];
        for (int[] range : collect) {
            if (range[1] < rMax)
                remove++;
            rMax = range[1];
        }
        /**/
        rest -= remove;
        return intervals.length - rest;
    }
}
